#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param: nums: a list of integers
    @return: The majority number that occurs more than 1/3
    """
    def majorityNumber(self, nums):
        cnt1 = cnt2 = 0
        slot1 = slot2 = None

        for ele in nums:
            if cnt1 == 0 or ele == slot1:
                cnt1 += 1
                slot1 = ele
            elif cnt2 == 0 or ele == slot2:
                cnt2 += 1
                slot2 = ele
            else:
                # 三个数不同(cnt1 和 cnt2一定大于0, 最少各有1个)
                cnt1 -= 1
                cnt2 -= 1

        results = self.check(slot1, slot2, nums)
        if results:
            return results[0]

        # for ele in nums:
    def check(self, cand_1, cand_2, nums):
        assert cand_1 != cand_2

        threshold = len(nums) / 3
        cnt1 = cnt2 = 0

        for ele in nums:
            if ele == cand_1:
                cnt1 += 1
            elif ele == cand_2:
                cnt2 += 1

        ret = []
        if cnt1 > threshold:
            ret.append(cand_1)
        if cnt2 > threshold:
            ret.append(cand_2)

        return ret


def main():
    print("start main")
    s = Solution()
    ret = s.majorityNumber([1,2,3,1, 2])
    print(ret)

if __name__ == "__main__":
    main()
